Parcours dans un graphe (1) - Corrigé

Énoncé

Le lycée de Lucie est situé à Paris proche de la station de métro Invalides. Elle a fait un relevé du plan de métro simplifié du quartier en utilisant seulement les stations suivantes :

• Champs-Élysées Clemenceau (CE)
  
• Châtelet (CH)
• Concorde (CO)
• Duroc (D)
• Charles de Gaulle Étoile (E)
  
• Franklin Roosevelt (F)
• Invalides (I)
• Montparnasse (M)
• La Motte Piquet Grenelle (MP)
• Odéon (O)
• Pasteur (P)
• Sèvres Babylone (S)
• Trocadéro (T)

Voici le graphe qu'elle a dessiné.

1. Peut-elle parcourir une fois et une seule chaque arête de ce graphe en partant de la station Invalides ?

2. Est-ce possible en partant d'une autre station ?

`` Solution

Dans ce graphe, il y a 13 sommets qui sont les stations de métro.

Sic sommets (F, T, CE, O, S et M) sont de degré trois (impair) donc, d'après le théorème d'Euler, il est impossible de trouver un chemin qui parcourt chaque arête une fois et une seule, d'où que l'on parte.